package chapter02_linkedList;

/**
 * 描述：
 *
 * @author hl
 * @date 2021/1/25 14:16
 */
public class RemoveMidNode {

    /**
     * 删除第a/b处的结点
     * @param head
     * @param a
     * @param b
     * @return
     */
    public Node removeByRatio(Node head, int a, int b){
        if (head == null || a > b || a < 1) {
            return head;
        }
        Node cur = head;
        int n = 0;
        while(cur != null){
            n++;
            cur = cur.next;
        }
        cur = head;
        n = (int) Math.ceil(((double)a * n) / b);
        if (n == 1) {
            return head.next;
        }
        while(--n != 1){
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return head;
    }

    /**
     * 删除链表的中间结点
     * 快慢指针
     * @param head
     * @return
     */
    public Node removeMidNode(Node head){
        if (head == null || head.next == null) {
            //只有一个结点，返回本身
            return head;
        }
        Node first = head.next;
        Node newHead = new Node(0);
        newHead.next = head;
        Node pre = newHead;
        //3,4->2;5,6->3;6,7;类推，只有第3,5,7...奇数个结点不为空，pre指针就后移一位
        while(first != null && first.next != null){
            pre = pre.next;
            first = first.next.next;
        }
        pre.next = pre.next.next;
        return newHead.next;
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        node.next = new Node(2);
//        node.next.next = new Node(3);
//        node.next.next.next = new Node(4);
//        node.next.next.next.next = new Node(5);
//        node.next.next.next.next.next = new Node(6);
//        node.next.next.next.next.next.next = new Node(7);
        new RemoveMidNode().removeMidNode(node);
    }
}
